This invention relates to a multiplexer configuration for a programmable logic device, and more particularly to a multiplexer configuration that consumes fewer logic resources for a given multiplexer function.
A multiplexer may be described as a hardware component that has N data inputs, C control inputs and only one data output. The data on the single output are the data on one of the N data inputs as determined by the state of the C control inputs. Every input can be output through a unique encoding of the C control inputs.
It is common in programmable logic devices to provide logic elements which are based on look-up tables. For example, programmable logic devices available from Altera Corporation, of San Jose, Calif., may include logic elements built around four-input look-up tables. The logic elements can be programmed and programmably interconnected to simulate any logic function, including that of a multiplexer.
One known configuration for implementing a multiplexer in programmable logic is to use two four-input look-up tables to create a four-to-one multiplexer (i.e., a multiplexer where N=4), or one four-input look-up table to create a two-to-one multiplexer. A tree of four-to-one multiplexers and/or two-to-one multiplexers can be used to create a multiplexer having any number of inputs, N, with up to N control inputs.
The control inputs can be encoded according to a binary scheme, requiring, for N data inputs, C control inputs where C=log2N or C=(INT(log2N)+1), depending on whether or not N is an integer power of 2, where INT(x) is a function that returns the largest integer in x (i.e., x rounded down to the nearest integer unless x is already an integer). Thus, for four inputs only two control inputs are required.
Larger multiplexers are created by creating trees of four-to-one binary-encoded multiplexers, each of which consumes two four-input look-up tables. Such a tree consumes at least 0.625N look-up tables for small N, and as N gets larger the most efficient trees approach 2N/3 look-up tables. And if N is such that one or more look-up table inputs are not used, the number of look-up tables required may be an even larger multiple of N, although it also may be possible to replace some of the four-to-one multiplexers with two-to-one multiplexers, each of which consumes only one look-up table, so the number of look-up tables may not increase as much.
The control inputs of a multiplexer also can be encoded using a scheme known as “one-hot” encoding, in which the number of control inputs equals the number of data inputs and only one control input is hot at any one time to select one of the data inputs as the output. It should be noted that although this scheme is referred to as “one-hot,” it may not be case that the signal voltage is high on only one control input. Rather, because signals are easily inverted, and may be inverted for various reasons, as long as the values loaded in the look-up table are adjusted accordingly, one or more inputs may have a high signal voltage without being considered “hot.” Thus, “one-hot” does not mean that only one input has a high signal voltage, or even that a high logic state is represented by a high signal voltage, or by the same signal voltage for all inputs. Rather, some signals that are high and some signals that are low may be considered to be in the same logic state, and “one-hot” means that only one input can be in the logic state that is considered high.
One method for constructing, from four-input look-up tables, an N-input multiplexer to be encoded using one-hot encoding requires a row of N/2 look-up tables. Each look-up table takes two data inputs and two control lines which are associated with those two data inputs. The look up table calculates a logic function equivalent to logically ANDing each data input with its associated control input and ORing the results of the two ANDs. The results of these N/2 look-up tables are ORed together to make the final multiplexer result. This requires a tree of four-input look-up tables, the number of which tends towards N/6. N/2+N/6=2N/3, so the efficiency is the same as the binary encoding case.
It would be desirable to be able to provide multiplexers in programmable logic that consume fewer of the programmable logic resources.